home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Bit_Set / Bit_Set.C next >
C/C++ Source or Header  |  1992-05-18  |  28KB  |  864 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. //
  13. // Created: MBN 06/13/89 -- Initial implementation
  14. // Updated: MBN 09/31/89 -- Added conditional exception handling
  15. // Updated: MBN 10/07/89 -- Changed operator[-~^&|] to allocate on stack
  16. //                          Bit_Set::find(int) returns state of indicated bit
  17. // Updated: MBN 10/12/89 -- Changed "current_position" to "curpos" and added
  18. //                          the current_position() method for Iterator<Type>
  19. // Updated: MBN 10/13/89 -- Changed from bit field to preprocessor bit macros
  20. // Updated: LGO 11/09/89 -- Major changes to every method
  21. // Updated: MBN 01/10/90 -- Fixed size-check bug in operator=
  22. // Updated: MJF 03/12/90 -- Added group names to RAISE
  23. // Updated: DLS 03/26/91 -- New lite version
  24. // Updated: VDN 05/01/92 -- Copying by bytes only, to avoid out of bounds.
  25. //
  26. // This file contains member and  friend function implementation  code for  the
  27. // Bit Set class defined in the  Bit_Set.h header file.  Where  appropriate and
  28. // possible,  interfaces to, and  us  of, existing system   functions  has been
  29. // incorporated.  An overview of the structure of the CoolBit_Set class, along with
  30. // a synopsis of each member and friend function, can be found in the Bit_Set.h
  31. // header file.
  32. //
  33.  
  34. #ifndef BIT_SET_H                // If no class definition
  35. #include <cool/Bit_Set.h>            // Include class specification
  36. #endif
  37.  
  38. #if defined(DOS)
  39. extern "C" {
  40. #include <string.h>                // For strcpy
  41. }
  42. #else
  43. #include <string.h>                // For strcpy
  44. #endif
  45.  
  46. #if defined(DOS)
  47. extern "C" {
  48. #include <stdlib.h>                // For exit()
  49. }
  50. #else
  51. #include <stdlib.h>                // For exit()
  52. #endif
  53.  
  54. #define BS_MAKE_POSITION(byte, offset) ((byte << 3) | offset)
  55. #define BS_BYTE_COUNT(n) ((int) (n + 7) >> 3)    // Byte count from bit count
  56.  
  57. extern int bit_pos[];                // Lowest/highest bit set masks
  58. extern int bits_set[];                // Number of bits set in mask
  59. extern int powers_of_2_minus_1[];        // Number of contiguous bits
  60.  
  61.  
  62. // CoolBit_Set -- Simple constructor that takes no arguments and allocates no
  63. //            storage
  64. // Input:     None
  65. // Output:    None
  66.  
  67. CoolBit_Set::CoolBit_Set () {
  68.   this->data = NULL;                // Zero initial memory
  69.   this->size = 0;                // Save number of bytes
  70.   this->number_elements = 0;            // Save number of elements
  71.   this->curpos = INVALID;            // Reset current position
  72.   this->growth_ratio = 0.0;            // Initialize growth ratio
  73.   if (alloc_size_s == 0) {
  74.     alloc_size_s = BIT_SET_BLK_SZ;        // Set memory block size
  75.   }
  76. }
  77.  
  78.  
  79. // CoolBit_Set -- Constructor that takes an integer argument specifying an initial
  80. //            number of elements for which storage must be allocated
  81. // Input:     Initial number of elements
  82. // Output:    None
  83.  
  84. CoolBit_Set::CoolBit_Set (int n) {
  85.   int nbyte = BS_BYTE_COUNT(n);
  86.   this->data = new unsigned char[nbyte];    // Allocate storage
  87.   for (int i = 0; i < nbyte; i++) data[i] = 0;    // Initialize bits to zero
  88.   this->size = nbyte;                // Save number of bytes
  89.   this->number_elements = 0;            // Save number of elements
  90.   this->curpos = INVALID;            // Reset current position
  91.   this->growth_ratio = 0.0;            // Initialize growth ratio
  92.   if (alloc_size_s == 0) {
  93.     alloc_size_s = BIT_SET_BLK_SZ;        // Set memory block size
  94.   }
  95. }
  96.  
  97.  
  98. // CoolBit_Set -- Constructor that takes a reference to another CoolBit_Set object and
  99. //            duplicates its size and value
  100. // Input:     Reference to Bit_Set object
  101. // Output:    None
  102.  
  103. CoolBit_Set::CoolBit_Set (const CoolBit_Set& b) {
  104.   this->data = new unsigned char[b.size];      // Allocate storage
  105.   for (int i = 0; i < b.size; i++)          // For each byte in vector
  106.     this->data[i] = b.data[i];              // Copy value
  107.   this->size = b.size;                  // Maintain number of bytes
  108.   this->number_elements = b.number_elements;      // Save number of elements
  109.   this->curpos = INVALID;              // Reset current position
  110.   this->growth_ratio = 0.0;              // Initialize growth ratio
  111.   if (alloc_size_s == 0) {
  112.     alloc_size_s = BIT_SET_BLK_SZ;          // Set memory block size
  113.   }
  114. }
  115.  
  116.  
  117. // ~CoolBit_Set -- Destructor for CoolBit_Set objects
  118. // Input:      None
  119. // Output:     None
  120.  
  121. CoolBit_Set::~CoolBit_Set () {
  122.   delete [] this->data;                // Free up memory allocated
  123. }
  124.  
  125. // MACRO generate_next(operation=, excess_a=0, excess_b=0) {
  126. //   int index, offset;
  127. //   long pos = this->curpos;
  128. //   if (pos == INVALID) {            // If invalid current position
  129. //     index = 0;                // Start at first byte
  130. //     offset = -1;                // Start at zero'th bit
  131. //   } else {
  132. //     index = BS_BYTE_NUMBER(pos);        // Get current byte index
  133. //     offset = BS_BYTE_OFFSET(pos);        // Get current bit offset
  134. //   }
  135. // 
  136. // #if excess_a || excess_b  
  137. //   int end = min(this->number_elements, b.number_elements);
  138. // #else
  139. //   int end = this->number_elements;
  140. // #endif
  141. //   register int value = (~powers_of_2_minus_1[offset+1]);
  142. //   while(index < end) {
  143. //     value &= this->data[index] operation;
  144. //     if (value != 0) goto found;
  145. //     value = -1;
  146. //     index++;
  147. //   }
  148. // #if excess_a || excess_b  
  149. //   if (index < (end = this->number_elements)) {
  150. // #if excess_a
  151. //     while(index < end) {
  152. //       value &= this->data[index];
  153. //       if (value != 0) goto found;
  154. //       value = -1;
  155. //       index++;
  156. //     }
  157. // #endif
  158. //   } else {
  159. // #if excess_b
  160. //     end = b.number_elements;
  161. //     while(index < end) {
  162. //       value &= b.data[index];
  163. //       if (value != 0) goto found;
  164. //       value = -1;
  165. //       index++;
  166. //     }
  167. // #endif
  168. //   }
  169. // #endif
  170. //   this->curpos = INVALID;            // Invalidate current position
  171. //   return FALSE;                // Return failure
  172. //  found:
  173. //   this->curpos = BS_MAKE_POSITION(index, bit_pos[value]); 
  174. //   return TRUE;                // Indicate success
  175. // }
  176.  
  177.  
  178. // next -- Increment the current position index
  179. // Input:  None
  180. // Output: Boolean TRUE/FALSE
  181.  
  182. Boolean CoolBit_Set::next () {
  183.   //generate_next()                             // take out this macro expansion
  184.   
  185.   int index, offset;
  186.   long pos = this->curpos;
  187.   if (pos == (-1)) {
  188.     index = 0;
  189.     offset = -1;
  190.   } else {
  191.     index = ((int) (pos >> 3));
  192.     offset = ((int) (pos & 0x07));
  193.   }
  194.   int end = this->number_elements;
  195.   register int value = (~powers_of_2_minus_1[offset+1]);
  196.   while(index < end) {
  197.     value &= this->data[index] ;
  198.     if (value != 0) goto found;
  199.     value = -1;
  200.     index++;
  201.   }
  202.   this->curpos = (-1);
  203.   return (0);
  204.  found:
  205.   this->curpos = ((index << 3) | bit_pos[value]);
  206.   return (1);
  207. }
  208.  
  209.  
  210. // next_intersection -- Position at the zero-relative integer of the next bit
  211. //                      in the intersection of two bit sets.
  212. // Input:               Reference to Bit Set object
  213. // Output:              TRUE/FALSE, current position updated
  214.  
  215. Boolean CoolBit_Set::next_intersection (const CoolBit_Set& b) {
  216.   if (this->number_elements > b.number_elements)
  217.     this->number_elements = b.number_elements;
  218.   //generate_next(&b.data[index],0,0)               // take out macro expansion
  219.   
  220.   int index, offset;
  221.   long pos = this->curpos;
  222.   if (pos == (-1)) {
  223.     index = 0;
  224.     offset = -1;
  225.   } else {
  226.     index = ((int) (pos >> 3));
  227.     offset = ((int) (pos & 0x07));
  228.   }
  229.   int end = this->number_elements;
  230.   register int value = (~powers_of_2_minus_1[offset+1]);
  231.   while(index < end) {
  232.     value &= this->data[index] &b.data[index];
  233.     if (value != 0) goto found;
  234.     value = -1;
  235.     index++;
  236.   }
  237.   this->curpos = (-1);
  238.   return (0);
  239.  found:
  240.   this->curpos = ((index << 3) | bit_pos[value]);
  241.   return (1);
  242. }
  243.  
  244.  
  245. // next_union -- Position at the zero-relative integer of the next bit in 
  246. //               the union of two bit sets.
  247. // Input:        Reference to Bit Set object
  248. // Output:       TRUE/FALSE, current position updated
  249.  
  250. Boolean CoolBit_Set::next_union (const CoolBit_Set& b) {
  251.   //generate_next(|b.data[index],1,1)         // take out macro expansion
  252.   
  253.   int index, offset;
  254.   long pos = this->curpos;
  255.   if (pos == (-1)) {
  256.     index = 0;
  257.     offset = -1;
  258.   } else {
  259.     index = ((int) (pos >> 3));
  260.     offset = ((int) (pos & 0x07));
  261.   }
  262.   int end = min(this->number_elements, b.number_elements);
  263.   register int value = (~powers_of_2_minus_1[offset+1]);
  264.   while(index < end) {
  265.     value &= this->data[index] |b.data[index];
  266.     if (value != 0) goto found;
  267.     value = -1;
  268.     index++;
  269.   }
  270.   if (index < (end = this->number_elements)) {
  271.     while(index < end) {
  272.       value &= this->data[index];
  273.       if (value != 0) goto found;
  274.       value = -1;
  275.       index++;
  276.     }
  277.   } else {
  278.     end = b.number_elements;
  279.     while(index < end) {
  280.       value &= b.data[index];
  281.       if (value != 0) goto found;
  282.       value = -1;
  283.       index++;
  284.     }
  285.   }
  286.   this->curpos = (-1);
  287.   return (0);
  288.  found:
  289.   this->curpos = ((index << 3) | bit_pos[value]);
  290.   return (1);
  291. }
  292.  
  293. // next_difference -- Position at the zero-relative integer of the next bit in 
  294. //                    the difference of two bit sets. That is all elements in
  295. //                    "this" that are not in "b"
  296. // Input:             Reference to Bit Set object
  297. // Output:            TRUE/FALSE, current position updated
  298.  
  299. Boolean CoolBit_Set::next_difference (const CoolBit_Set& b) {
  300.   //generate_next(&~b.data[index],1,0)      // take out macro expansion
  301.   
  302.   int index, offset;
  303.   long pos = this->curpos;
  304.   if (pos == (-1)) {
  305.     index = 0;
  306.     offset = -1;
  307.   } else {
  308.     index = ((int) (pos >> 3));
  309.     offset = ((int) (pos & 0x07));
  310.   }
  311.   int end = min(this->number_elements, b.number_elements);
  312.   register int value = (~powers_of_2_minus_1[offset+1]);
  313.   while(index < end) {
  314.     value &= this->data[index] &~b.data[index];
  315.     if (value != 0) goto found;
  316.     value = -1;
  317.     index++;
  318.   }
  319.   if (index < (end = this->number_elements)) {
  320.     while(index < end) {
  321.       value &= this->data[index];
  322.       if (value != 0) goto found;
  323.       value = -1;
  324.       index++;
  325.     }
  326.   } else {
  327.   }
  328.   this->curpos = (-1);
  329.   return (0);
  330.  found:
  331.   this->curpos = ((index << 3) | bit_pos[value]);
  332.   return (1);
  333. }
  334.  
  335. // next_xor -- Position at the zero-relative integer of the next bit in 
  336. //             the XOR of two bit sets.
  337. // Input:      Reference to Bit Set object
  338. // Output:     TRUE/FALSE, current position updated
  339.  
  340. Boolean CoolBit_Set::next_xor (const CoolBit_Set& b) {
  341.   //generate_next(^b.data[index];,1,1)     // take out macro expansion
  342.   
  343.   int index, offset;
  344.   long pos = this->curpos;
  345.   if (pos == (-1)) {
  346.     index = 0;
  347.     offset = -1;
  348.   } else {
  349.     index = ((int) (pos >> 3));
  350.     offset = ((int) (pos & 0x07));
  351.   }
  352.   int end = min(this->number_elements, b.number_elements);
  353.   register int value = (~powers_of_2_minus_1[offset+1]);
  354.   while(index < end) {
  355.     value &= this->data[index] ^b.data[index];;
  356.     if (value != 0) goto found;
  357.     value = -1;
  358.     index++;
  359.   }
  360.   if (index < (end = this->number_elements)) {
  361.     while(index < end) {
  362.       value &= this->data[index];
  363.       if (value != 0) goto found;
  364.       value = -1;
  365.       index++;
  366.     }
  367.   } else {
  368.     end = b.number_elements;
  369.     while(index < end) {
  370.       value &= b.data[index];
  371.       if (value != 0) goto found;
  372.       value = -1;
  373.       index++;
  374.     }
  375.   }
  376.   this->curpos = (-1);
  377.   return (0);
  378.  found:
  379.   this->curpos = ((index << 3) | bit_pos[value]);
  380.   return (1);
  381. }
  382.  
  383.  
  384. // prev -- Decrement the current position index
  385. // Input:  None
  386. // Output: Boolean TRUE/FALSE
  387.  
  388. Boolean CoolBit_Set::prev () {
  389.   int index, value, offset;
  390.   long pos = this->curpos;
  391.   if (pos == INVALID) {                // If invalid current position
  392.     index = this->number_elements;        // Start at last byte
  393.     offset = BS_BITSPERBYTE;            // Start at last bit bit
  394.   } else {
  395.     index = BS_BYTE_NUMBER(pos);        // Get current byte index
  396.     offset = BS_BYTE_OFFSET(pos);        // Get current bit offset
  397.   }
  398.   value = (this->data[index] & 
  399.        (~powers_of_2_minus_1[offset-1]));    //Reset low bits
  400.   while (value == 0) {                // If no more bits set
  401.     if (index <0){                // If we are at start of vector
  402.       this->curpos = INVALID;            // Invalidate current position
  403.       return FALSE;                // Return failure
  404.     }
  405.     value = this->data[--index];        // Else get next byte value
  406.   }
  407.     this->curpos = BS_MAKE_POSITION(index,bit_pos[value]);
  408.   return TRUE;                    // Indicate success
  409. }
  410.  
  411.  
  412. // find -- Set the current position to the nth bit
  413. // Input:  Bit position desired (really, it's an integer value)
  414. // Output: TRUE/FALSE
  415.  
  416. Boolean CoolBit_Set::find (int n) {
  417. #if ERROR_CHECKING
  418.   if (BS_BYTE_NUMBER(n) >= this->size) {    // If outside allocated range
  419.     this->find_error (n);            // Raise exception
  420.     this->curpos = INVALID;            // Invalidate current position
  421.     return FALSE;                // Return failure
  422.   }
  423. #endif
  424.     this->curpos = n;
  425.   return(((this->data[BS_BYTE_NUMBER(n)]) >> BS_BYTE_OFFSET(n)) & 0x01);
  426. }
  427.  
  428.  
  429. // put -- Put an element to the set
  430. // Input: Bit position desired (really, it's an integer value)
  431. // Output: TRUE/FALSE
  432.  
  433. Boolean CoolBit_Set::put (int n) {
  434.   int nbytes = BS_BYTE_COUNT(n+1);        // Calculate byte index
  435.   if (nbytes >= this->number_elements) {    // If bigger than largest
  436.     if (nbytes >= this->size)            // If outside allocated range
  437.       this->grow (n);                // Grow the bit vector
  438.     this->number_elements = nbytes;
  439.   }
  440.   this->data[BS_BYTE_NUMBER(n)] |= (1 << BS_BYTE_OFFSET(n)); // Set proper bit
  441.   this->curpos = n;
  442.   return TRUE;                    // Return success
  443. }
  444.  
  445.  
  446. // put -- Put a range of elements to the set
  447. // Input: Start, end bit positions (really, they're just integer values)
  448. // Output: TRUE/FALSE
  449.  
  450. Boolean CoolBit_Set::put (int start, int end) {
  451.   if (start > end) {                // If start is passed the end!
  452. #if ERROR_CHECKING
  453.     this->put_error (start,end);        // Raise exception
  454. #endif
  455.     this->curpos = INVALID;            // Invalidate current position
  456.     return FALSE;                // Return failure
  457.   }
  458.   int last = BS_BYTE_COUNT(end);
  459.   if (last >= this->number_elements) {
  460.     if (last >= this->size)
  461.       this->grow (end);                // Grow the bit vector
  462.     this->number_elements = last;
  463.   }
  464.   // This could be made MUCH faster by banging a byte at a time
  465.   for (int i = start; i <= end; i++) // For each element in range
  466.     this->data[BS_BYTE_NUMBER(i)] |= (1 << (BS_BYTE_OFFSET(i))); // Set bit
  467.   this->curpos = start;
  468.   return TRUE;                    // Return success
  469. }
  470.  
  471.  
  472. // remove -- Remove element from set at current position
  473. // Input:    None
  474. // Output:   TRUE/FALSE
  475.  
  476. Boolean CoolBit_Set::remove () {
  477. #if ERROR_CHECKING
  478.   if (this->curpos == INVALID) {        // If current position INVALID
  479.     this->remove_error ();            // Raise exception
  480.     return FALSE;                // Return failure
  481.   }
  482. #endif
  483.   int mask = ~(1 << BS_BYTE_OFFSET(this->curpos)); // Make bit mask
  484.   this->data[BS_BYTE_NUMBER(this->curpos)] &= mask; // Turn off bit
  485.   return TRUE;
  486. }
  487.  
  488.  
  489. // remove -- Remove the specified element from the set
  490. // Input:    Element to be removed (really just an integer value)
  491. // Output:   TRUE/FALSE
  492.  
  493. Boolean CoolBit_Set::remove (int n) {
  494.   if (BS_BYTE_NUMBER(n) >= this->number_elements) // If out of range
  495.     return FALSE;                  // Return failure
  496.   int mask = ~(1 << BS_BYTE_OFFSET(n));          // Make bit mask
  497.   this->data[BS_BYTE_NUMBER(n)] &= mask;      // Turn off bit
  498.   this->curpos = n;
  499.   return TRUE;                    // Return success
  500. }
  501.  
  502.  
  503. // remove -- Remove range of elements from the set
  504. // Input:    Start, end bit positions (really, they're just integer values)
  505. // Output:   TRUE/FALSE
  506.  
  507. Boolean CoolBit_Set::remove (int start, int end) {
  508. #if ERROR_CHECKING
  509.   if (start > end) {
  510.     this->rem_start_end_error (start,end);    // Raise exception
  511.     this->curpos = INVALID;            // Invalidate current pos
  512.     return FALSE;                // Return failure
  513.   }
  514. #endif
  515.     if (BS_BYTE_NUMBER(start) >= this->number_elements) {
  516.     this->curpos = INVALID;            // Invalidate current pos
  517.     return FALSE;                // Return failure
  518.   }
  519.   if (BS_BYTE_NUMBER(end) >= this->number_elements)
  520.     end = this->number_elements * BS_BITSPERBYTE;
  521.   for (int i = start; i <= end; i++)         // For each element in range
  522.     this->data[BS_BYTE_NUMBER(i)] &= ~(1 << (BS_BYTE_OFFSET(i))); // Reset bit
  523.   this->curpos = start;
  524.   return TRUE;                    // Return success
  525. }
  526.  
  527.  
  528. // search -- Determine if one Bit Set is a subset of another
  529. // Input:    Reference to a Bit Set object
  530. // Output:   TRUE/FALSE
  531.  
  532. Boolean CoolBit_Set::search (const CoolBit_Set& b) const {
  533.   int len = min(this->number_elements, b.number_elements);
  534.   for (int i = 0; i < len; i++)            // For each byte in set
  535.     if ((this->data[i] & b.data[i]) != b.data[i]) // If not as first set
  536.       return FALSE;                  // Then not a subset
  537.   if (i < b.number_elements)              // If more elements in 2nd
  538.     for (; i < b.number_elements; i++)          // Its still subset if all
  539.       if (b.data[i] != 0)              // other elemenst are 0
  540.     return FALSE;                  // Nope! Return failure
  541.   return TRUE;                      // Subset; return success
  542. }
  543.  
  544.  
  545. // operator- -- Overload unary minus operator to return elements not in set
  546. // Input:       None
  547. // Output:      Bit Set object containing complement of this set
  548.  
  549. CoolBit_SetE CoolBit_Set::operator- () {
  550.   CoolBit_Set temp (this->number_elements * BS_BITSPERBYTE);    // New bit set
  551.   for (int i = 0; i < this->number_elements; i++) // For each byte in vector
  552.     temp.data[i] = ~(this->data[i]);        // Copy complement of set
  553.   temp.curpos = INVALID;            // Reset current position
  554.   temp.number_elements = this->number_elements; // Update number of elements
  555.   CoolBit_SetE& result = (CoolBit_SetE&) temp;    // same physical object
  556.   return result;                // shallow swap on return
  557. }
  558.  
  559.  
  560. // MACRO generate_set_operator(a, b, op, excess=0) {
  561. //   int a_size = BS_WORD_COUNT(a->number_elements);
  562. //   int b_size = BS_WORD_COUNT(b.number_elements);
  563. //   unsigned int* a_data = (unsigned int*) a->data;
  564. //   unsigned int* b_data = (unsigned int*) b.data;
  565. //   int min_size = min(a_size, b_size);
  566. //   for (int i = 0; i < min_size; i++)
  567. //     a_data[i] = a_data[i] op b_data[i];        // 
  568. //   for (; i < b_size; i++)
  569. //     a_data[i] = excess;                // operate on excess b's
  570. // }
  571.  
  572.  
  573. #define generate_set_operator(a, b, op, excess)                          \
  574.   int a_size = a->number_elements;                                \
  575.   int b_size = b.number_elements;                                 \
  576.   unsigned char* a_data = a->data;                            \
  577.   unsigned char* b_data = b.data;                             \
  578.   int min_size = min(a_size, b_size);                         \
  579.   for (int i = 0; i < min_size; i++)                          \
  580.      a_data[i] = a_data[i] op b_data[i];    /*operate on common sets*/    \
  581.   for (; i < b_size; i++)                                       \
  582.      a_data[i] = excess;            /*operate on excess b's*/
  583.  
  584.  
  585. // operator|= -- Determine the union of two sets, that is all elements in each
  586. //               set and destructively modify the first set with the result
  587. // Input:        Reference to a bit set
  588. // Output:       Updated Bit Set object containing union of two sets
  589.  
  590. CoolBit_Set& CoolBit_Set::operator|= (const CoolBit_Set& b) {
  591.   if (b.number_elements > this->size)
  592.     this->grow(b.number_elements * BS_BITSPERBYTE);
  593.   generate_set_operator(this, b, |, b_data[i]); // Calculate the union
  594.   if (this->number_elements < b.number_elements)
  595.     this->number_elements = b.number_elements;
  596.   this->curpos = INVALID;            // Invalidate current position
  597.   return *this;                    // Return refenerce
  598. }
  599.  
  600.  
  601. // operator-= -- Determine the difference of two sets, that is all elements in
  602. //               the first set that are not in the second and destructively
  603. //               modify the first with the result
  604. // Input:        Reference to bit set
  605. // Output:       Updated Bit Set object containing union of two sets
  606.  
  607. CoolBit_Set& CoolBit_Set::operator-= (const CoolBit_Set& b) {
  608.   generate_set_operator(this, b, &~, 0);    // Calculate the difference
  609.   this->curpos = INVALID;            // Invalid current position
  610.   return *this;                    // Return refenerce
  611. }
  612.  
  613.  
  614. // operator^= -- Determine the exclusive-OR of two sets, that is all elements
  615. //               in the first set that are not in the second and all elements
  616. //               in the second set that are not in the first and destructively 
  617. //               modify the first with the result
  618. // Input:        Reference to bit set
  619. // Output:       Updated Bit Set object containing XOR of two sets
  620.  
  621. CoolBit_Set& CoolBit_Set::operator^= (const CoolBit_Set& b) {
  622.   if (b.number_elements > this->size)
  623.     this->grow(b.number_elements * BS_BITSPERBYTE);
  624.   generate_set_operator(this, b, ^, b_data[i]); // Calculate the exclusive-OR
  625.   if (this->number_elements < b.number_elements)
  626.     this->number_elements = b.number_elements;
  627.   this->curpos = INVALID;            // Invalidate current position
  628.   return *this;                    // Return refenerce
  629. }
  630.  
  631.  
  632. // operator&= -- Determine the intersection of two sets, that is all elements 
  633. //               that are in both sets and destructively modify the first with
  634. //               the result
  635. // Input:        Reference to Bit Set object
  636. // Output:       Updated Bit Set object containing intersection of two sets
  637.  
  638. CoolBit_Set& CoolBit_Set::operator&= (const CoolBit_Set& b) {
  639.   generate_set_operator(this, b, &, 0);        // Calculate the exclusive-OR
  640.   if (this->number_elements > b.number_elements) {
  641.     this->number_elements = b.number_elements;    // shorten ourself
  642.     for (; i < a_size; i++) a_data[i] = 0;    // and Zap excess bits
  643.   }
  644.   this->curpos = INVALID;            // Invalid current position
  645.   return *this;                    // Return refenerce
  646. }
  647.  
  648.  
  649. // clear -- Remove all elements from the set
  650. // Input:   None
  651. // Output:  None
  652.  
  653. void CoolBit_Set::clear () {
  654.   for (int i = 0; i < this->number_elements; i++) 
  655.     this->data[i] = 0;                // Initialize bits to zero
  656.   this->curpos = INVALID;            // Invalidate current position
  657. }
  658.  
  659.  
  660. // grow -- resize the bit set (private method)
  661. // Input:    Minimum size requirement
  662. // Output:   none
  663.  
  664. void CoolBit_Set::grow (int min_size) {
  665.   if (this->growth_ratio != 0.0 &&
  666.       (this->size * (1.0+growth_ratio)) >= min_size)
  667.     min_size = (int)(this->size * (1.0 + growth_ratio)); // New size
  668.   else
  669.     min_size += alloc_size_s;            // Update vector size
  670.   resize(min_size);
  671. }
  672.  
  673.  
  674. // resize -- Resize the bit set for at least some specified number of elements
  675. // Input:    Minimum size requirement
  676. // Output:   TRUE/FALSE
  677.  
  678. void CoolBit_Set::resize (int n) {
  679.   int nbytes = BS_BYTE_COUNT(n);
  680.   unsigned char* temp = new unsigned char[nbytes]; // Allocate storage
  681.   for (int i = 0; i < this->number_elements; i++) 
  682.     temp[i] = this->data[i];            // copy old data
  683.   for (; i < nbytes; i++)
  684.     temp[i] = 0;                // clear new data
  685.   delete [] this->data;                // Free old storage
  686.   this->data = temp;                // Point to new storage
  687.   this->size = nbytes;                // Save number of bytes
  688.   this->curpos = INVALID;            // Reset current position
  689. }
  690.  
  691.  
  692. // operator= -- Overload the assignment operator for Bit Set objects
  693. // Input:       Reference to Bit Set object
  694. // Output:      Reference to Bit Set object
  695.  
  696. CoolBit_Set& CoolBit_Set::operator= (const CoolBit_Set& b) {
  697.   if (this != &b) {
  698.     int len = b.size;                // Get size of object to copy
  699.     if (this->size < len) {            // If not enough storage
  700.       delete [] this->data;            // Deallocate old storage
  701.       this->data = new unsigned char[len];    // Allocate same size storage
  702.       this->size = len;                // Maintain number of bytes
  703.     }
  704.     for (int i = 0; i < len; i++)
  705.       this->data[i] = b.data[i];        // copy all bytes
  706.     this->number_elements = b.number_elements;
  707.     this->curpos = INVALID;            // Reset current position
  708.   }
  709.   return *this;                    // Return reference to object
  710. }
  711.  
  712.  
  713. // operator<< -- Overload the output operator for Bit Set objects
  714. // Input:        Reference to stream, reference to Bit Set object
  715. // Output:       Reference to stream
  716.  
  717. ostream& operator<< (ostream& os, const CoolBit_Set& b) {
  718.   static char ascii_rep[10];            // Static storage for 0's/1's
  719.   os << "[ ";                    // Output start of set bracket
  720.   for (int i = 0; i < b.number_elements; i++) {    // For each byte in the set
  721.     strcpy (ascii_rep, "00000000 ");        // Assume majority of zeros
  722.     for (int j = 7; j >= 0; j--)
  723.       if (b.data[i] & (1 << j))
  724.     ascii_rep[j] = '1';            // Copy "1" character to string
  725.     os << ascii_rep;                // Output 0's and 1's for byte
  726.   }
  727.   os << "]\n";                    // Output terminating bracket
  728.   return os;                    // Return reference to stream
  729. }
  730.  
  731.  
  732. // operator== -- Overload the equality operator for Bit Set objects
  733. // Input:        Reference to Bit Set object
  734. // Output:       TRUE/FALSE
  735.  
  736. Boolean operator== (const CoolBit_Set& b1, const CoolBit_Set& b2) {
  737.   int len = min(b1.number_elements, b2.number_elements); // common length
  738.   for (int i = 0; i < len; i++)                   
  739.     if (b1.data[i] != b2.data[i])          // Check for different bits
  740.       return FALSE;                  // in common section
  741.   for (i = len; i < b1.number_elements; i++)      // Check for nonzero bits in
  742.     if (b1.data[i])                  // extra section of this
  743.       return FALSE;                  
  744.   for (i = len; i < b2.number_elements; i++)      // Check for nonzero bits in
  745.     if (b2.data[i])                  // extra section of b
  746.       return FALSE;                  
  747.   return TRUE;                      // Return success indication
  748. }
  749.  
  750.  
  751. // length -- Return number of elements in Set
  752. // Input:    None
  753. // Output:   Integer representing number of bits set 
  754.  
  755. int CoolBit_Set::length () const {
  756.   int count = 0;                // Temporary to hold count
  757.   int len = this->number_elements;
  758.   for (int i = 0; i < len; i++)            // For each byte in the vector
  759.     count += bits_set[this->data[i]];        // Add to count number bits set
  760.   return count;                    // Return element count 
  761. }
  762.  
  763.  
  764. // value_error -- Raise exception for CoolBit_Set::value() method
  765. // Input:         None
  766. // Output:        None
  767.  
  768. void CoolBit_Set::value_error () const {
  769.   //RAISE (Error, SYM(CoolBit_Set), SYM(Invalid_Cpos),
  770.   printf ("CoolBit_Set::value(): Invalid current position.\n");
  771.   abort ();
  772. }
  773.  
  774.  
  775. // bracket_error -- Raise exception for CoolBit_Set::operator[]() method
  776. // Input:           None
  777. // Output:          None
  778.  
  779. void CoolBit_Set::bracket_error (int n) const {
  780.   //RAISE (Error, SYM(CoolBit_Set), SYM(Out_Of_Range),
  781.   printf ("CoolBit_Set::operator[](): Bit number %d out of range.\n", n);
  782.   abort ();
  783. }
  784.  
  785.  
  786. // find_error -- Raise exception for CoolBit_Set::find() method
  787. // Input:        None
  788. // Output:       None
  789.  
  790. void CoolBit_Set::find_error (int n) const {
  791.   //RAISE (Error, SYM(CoolBit_Set), SYM(Out_Of_Range),
  792.   printf ("CoolBit_Set::find(): Bit number %d out of range.\n", n);
  793.   abort ();
  794. }
  795.  
  796.  
  797. // put_error -- Raise exception for CoolBit_Set::put() method
  798. // Input:       Start, end bit positions
  799. // Output:      None
  800.  
  801. void CoolBit_Set::put_error (int start, int end) const {
  802.   //RAISE (Error, SYM(CoolBit_Set), SYM(Invalid_Start_End),
  803.   printf ("CoolBit_Set::put(): Start bit %d greater than end bit %d.\n",
  804.       start, end);
  805.   abort ();
  806. }
  807.  
  808.  
  809. // remove_error -- Raise exception for CoolBit_Set::remove() method
  810. // Input:          None
  811. // Output:         None
  812.  
  813. void CoolBit_Set::remove_error () const {
  814.   //RAISE (Error, SYM(CoolBit_Set), SYM(Invalid_Cpos),
  815.   printf ("CoolBit_Set::remove(): Invalid current position.\n");
  816.   abort ();
  817. }
  818.  
  819.  
  820. // rem_start_end_error -- Raise exception for CoolBit_Set::remove(int,int) method
  821. // Input:                 Start, end bit positions
  822. // Output:                None
  823.  
  824. void CoolBit_Set::rem_start_end_error (int start, int end) const {
  825.   //RAISE (Error, SYM(CoolBit_Set), SYM(Invalid_Start_End),
  826.   printf ("CoolBit_Set::remove(): Start bit %d greater than end bit %d.\n",
  827.       start, end);
  828.   abort ();
  829. }
  830.  
  831.  
  832. // void set_growth_ratio (float) -- Set the growth percentage for the Vector
  833. //                                  object.
  834. // Input:                           Float ratio, type
  835. // Output:                          None
  836.  
  837. void CoolBit_Set::set_growth_ratio (float ratio) {
  838. #if ERROR_CHECKING
  839.   if (ratio <= 0.0) {                // If non-positive growth
  840.     //RAISE (Error, SYM(CoolBit_Set), SYM(Negative_Ratio),
  841.     printf ("CoolBit_Set::set_growth_ratio(): Negative growth ratio %f.\n",
  842.         ratio);
  843.     abort ();
  844.   }
  845. #endif
  846.   this->growth_ratio = ratio;            // Adjust ration
  847. }
  848.  
  849.  
  850. // void set_alloc_size (int) -- Set the default allocation size growth rate.
  851. // Input:                       Growth size in number of elements, type
  852. // Output:                      None
  853.  
  854. void CoolBit_Set::set_alloc_size (int n) {
  855. #if ERROR_CHECKING
  856.   if (n < 0) {                    // If index out of range
  857.     //RAISE (Error, SYM(CoolBit_Set), SYM(Negative_Size),
  858.     printf ("CoolBit_Set::set_alloc_size(): Negative growth size %d.\n", n);
  859.     abort ();
  860.   }
  861. #endif
  862.   this->alloc_size_s = n;            // Set growth size
  863. }
  864.